Computer simulation has become an important tool for studying and interpreting various physical processes. This technique presents, however, considerable limits in relation to its aims and to the accuracy of the results, owing to the stringent requirements in terms of computational power that are difficult to meet even using the most advanced supercomputers. Simulating a very complex model calls for supplementary computing power as the number of parameters of the model increases.
One way to address this problem is to supply the computing power used by exploiting a network of computers (servers) connected to one another. From the user's standpoint, this approach is desired to be transparent. It is desirable, in fact, that the network should appear as a single large virtual supercomputer. This new computational paradigm is called “grid.” Providing an integrated computing-grid environment may make it possible to give rise to computing infrastructures with incomparable potential.
From the conceptual standpoint, a grid is simply a set of computational resources that perform tasks or jobs assigned to it. It appears to the users as a single large system that offers a single access point with distributed and powerful resources. The users treat the grid as a single computational resource. The grid accepts the tasks assigned by the users and allocates them selectively (i.e., “schedules” them) in view of their execution on suitable systems comprised in the grid on the basis of resource-management policies. The users can thus entrust to the grid tasks that are even rather burdensome (for example, many activities to be carried out in a short time), without having to be concerned as to where the tasks will materially be carried out.
The main advantages linked to the use of a computational grid (the so-called “Grid Computing”) are reduction of hardware costs, balancing of the job load between the various “machines” (via a load management system), capacity for managing heterogeneous systems, increase in productivity, and lower exposure to hardware obsolescence.
In actual fact, however, it is difficult to define a system approach to the management of the grid resources to be really transparent for the users. This is chiefly due to the heterogeneous architectural characteristics of the grid.
In this connection, one may think that the users of the grid may implement a manual approach to allocating the resources of the grid (carried out via job-description tools, i.e., using JDL (Job Description Language) script. This approach puts the choice and estimation of the resources used at the disposal of the user of the grid, and this inevitably implies a risk of overestimation or underestimation of the resources due to human error, with consequent waste of the resources of the grid (see in this connection the article by Spata, et al. entitled, “Agent-based negotiation techniques for a Grid: the Prophet Agents”, 2nd IEEE International Conference on e-Science and Grid Computing 2006.
There have on the other hand already been experiments in the computer-program sector of the application of principles and criteria drawn from the world of economy (see, for example, the article by D. Ferguson, et al. entitled, “Economic models for allocating resources in computer systems”, in Scott Learwater, Editor, “Market-Based Control: A Paradigm for Distributed Resource Allocation”, World Scientific, Hong Kong, 1996 and the article by Y. K. Kwok, et al. entitled, “Non-Cooperative Grids: Game Theoretic Modeling and Strategy Optimization”, submitted to IEEE Trans. Parallel and Distributed Systems, December 2004).
In the article by D. Ferguson, et al. entitled, “Economic models for allocating resources in computer systems”, it is shown that, by applying a scheduling algorithm based upon the so-called Nash equilibrium as economic model for distributed systems, the average queuing time decreases when the use of the system resources increases. On the other hand, it has been shown that, using the optimal algorithm, if the use of the resources increases, the average queuing time increases also. In fact, starting from a queue with zero load, with homogeneous jobs belonging to the same class, it emerges that the scheduling procedure based upon Nash equilibrium is advantageous only if the utilization factor per queue (understood as container of homogeneous computational servers) is higher than an agreed threshold time. In fact, when the queue has emptied and the jobs have an average duration shorter, for example, than one hour, the scheduling algorithms based upon balancing of the load operate already very well. The problem starts to arise when the jobs last on average more than one hour, loading heavily the CPU (jobs of a CPU-bound type).
In the article by Y. K. Kwok, et al. entitled, “Non-Cooperative Grids: Game Theoretic Modeling and Strategy Optimization”, three different scheduling procedures are compared: Nash equilibrium, random, and MinMin (optimal). Here, the results show that the approaches based upon game theory and on Nash equilibrium are very similar to a random-planning strategy, while the Pareto-optimal algorithm (MinMin) proves to be the best scheduling algorithm. In this document, no information is given on the system-utilization factor, ρ. In fact, the main problem of scheduling procedures based upon optimal strategies (i.e., MinMin) lies in that they can be applied advantageously only when the value of this factor remains lower than a given threshold x.